package tree

import (
	//"fmt"
	"bytes"
	"container/list"
	"encoding/gob"
	"errors"
	"fmt"
	"math"
	"reflect"
)

func DeepCopy(dst , src interface{})error{
	var buffer bytes.Buffer
	if err := gob.NewEncoder(&buffer).Encode(src) ; err != nil {
		return err
	}
	return gob.NewDecoder(&buffer).Decode(dst)
}

// type TreeData interface{
// 	GetData()interface{}
// 	SetData(TreeData)
// 	Compare(TreeData)(int, error)
// }

// type BaseTreeData struct{
// 	Value interface{}
// }


type BinTree interface{
	GetLeftChild()BinTree
	SetLeftChild(BinTree)
	GetRightChild()BinTree
	SetRightChild(BinTree)
	GetData()interface{}
}

// LL型
func LLRotation(b BinTree)BinTree{
	oldAvl := b
	newAvl := oldAvl.GetLeftChild()
	oldAvl.SetLeftChild(newAvl.GetRightChild())
	newAvl.SetRightChild(oldAvl)
	return newAvl
}

// LR型
func LRRotation(b BinTree)BinTree{
	b.SetLeftChild(RRRotation(b.GetLeftChild()))
	return LLRotation(b)
}

// RR型
func RRRotation(b BinTree)BinTree{
	oldAvl := b
	newAvl := oldAvl.GetRightChild()
	oldAvl.SetRightChild(newAvl.GetLeftChild())
	newAvl.SetLeftChild(oldAvl)
	return newAvl
}

// RL型
func RLRotation(b BinTree)BinTree{
	b.SetRightChild(LLRotation(b.GetRightChild()))
	return RRRotation(b)
}

// 比较
func Compare(node1 , node2 BinTree)(int, error){
	if node1 == nil {
		return -2 , errors.New("node1 is nil")
	}
	if node2 == nil {
		return -2 , errors.New("node2 is nil")
	}
	// 默认使用 int 作为value类型
	if reflect.DeepEqual(node1.GetData(), node2.GetData()) {
		return 0 , nil
	}else {
		v1 , ok := node1.GetData().(int)
		if !ok {
			return -2, errors.New("node1.Value turn failed")
		}
		v2 , ok := node2.GetData().(int)
		if !ok {
			return -2, errors.New("node2.Value turn failed")
		}
		if v1 > v2 {
			return 1 , nil
		}
		if v1 == v2 {
			return 0, nil
		}
		return -1, nil
	}
}

// 插入
func Insert(root, node BinTree)(BinTree, error){
	if node == nil {
		return nil, errors.New("node is nil ! ")
	}
	if root == nil || root.GetData() == nil {
		return node , nil
	}
	cur := root
	for cur != nil {
		res, err := Compare(cur, node)
		if err != nil {
			return nil, err
		}
		switch res {
		case -1 :
			if cur.GetRightChild() == nil {
				cur.SetRightChild(node)
				return cur, nil
			}
			cur = cur.GetRightChild()
		case 0 :
			return cur , nil
		case 1:
			if cur.GetLeftChild() == nil {
				cur.SetLeftChild(node)
				return cur , nil
			}
			cur = cur.GetLeftChild()
		}
	}
	return cur, nil
}

// 中序遍历Morris方法 时间复杂度O(n), 空间复杂度o(1)
func InOrderMorris(root BinTree) (res []interface{}) {
	res = make([]interface{}, 0, 1024)
	for root != nil {
		if root.GetLeftChild() != nil {
			p := root.GetLeftChild()
			for p.GetRightChild() != nil && p.GetRightChild() != root {
				p = p.GetRightChild()
			}
			if p.GetRightChild() == nil {
				p.SetRightChild(root)
				root = root.GetLeftChild()
			} else if p.GetRightChild() == root {
				res = append(res, root.GetData())
				p.SetRightChild(nil)
				root = root.GetRightChild()
			}
		} else {
			res = append(res, root.GetData())
			root = root.GetRightChild()
		}
	}
	return
}

// 递归中序
func InOrderRecursion(root BinTree) (res []interface{}) {
	res = make([]interface{}, 0, 1024)
	if root == nil {
		return nil
	}
	var dfs func(node BinTree)
	dfs = func(node BinTree) {
		if node == nil {
			return
		}
		dfs(node.GetLeftChild())
		res = append(res, node.GetData())
		dfs(node.GetRightChild())
	}
	dfs(root)
	return
}

// 递归前序
func PreOrderRecursion(root BinTree) (res []interface{}) {
	res = make([]interface{}, 0, 1024)
	if root == nil {
		return nil
	}
	var dfs func(node BinTree)
	dfs = func(node BinTree) {
		if node == nil {
			return
		}
		res = append(res, node.GetData())
		dfs(node.GetLeftChild())
		dfs(node.GetRightChild())
	}
	dfs(root)
	return
}

// 递归后续
func PostOrderRecursion(root BinTree) (res []interface{}) {
	res = make([]interface{}, 0, 1024)
	if root == nil {
		return nil
	}
	var dfs func(node BinTree)
	dfs = func(node BinTree) {
		if node == nil {
			return
		}
		dfs(node.GetLeftChild())
		dfs(node.GetRightChild())
		res = append(res, node.GetData())
	}
	dfs(root)
	return
}

// 树的层级遍历, 就是广度优先
func HierarchicalTraversal(root BinTree)(res []interface{}){
	if root == nil {
		return nil
	}
	res = make([]interface{}, 0, 1024)
	sequeue := list.New()
	sequeue.PushBack(root)
	for sequeue.Len() > 0 {
		//fmt.Println(sequeue)
		node, _ := sequeue.Remove(sequeue.Front()).(BinTree)
		res = append(res, node.GetData())
		if node != nil {
			if node.GetLeftChild() != nil {
				sequeue.PushBack(node.GetLeftChild())
			}
			if node.GetRightChild() != nil {
				sequeue.PushBack(node.GetRightChild())
			}
		}
	}
	return
} 


type BaseBinTree struct {
	Value interface{}
	LChild *BaseBinTree
	RChild *BaseBinTree
}

func (b *BaseBinTree)GetLeftChild()BinTree{
	if b.LChild == nil {
		return nil
	}
	return b.LChild
}

func (b *BaseBinTree)SetLeftChild(node BinTree){
	b.LChild, _ = node.(*BaseBinTree)
}

func (b *BaseBinTree)GetRightChild()BinTree{
	if b.RChild == nil {
		return nil
	}
	return b.RChild
}

func (b *BaseBinTree)SetRightChild(node BinTree){
	b.RChild, _ = node.(*BaseBinTree)
}

func (b *BaseBinTree)GetData()interface{}{
	if b.Value == nil {
		return nil
	}
	return b.Value
}

// 生成树
// BFS DFS 层序
// 二叉树排序

//生成的是一颗单边的极端的树
func CreateTree2(data []interface{})(root *BaseBinTree){
	if len(data) == 0 {
		return nil
	}
	root = new(BaseBinTree)
	root.Value = data[0]
	for _,  v :=  range data[1:] {
		node := new(BaseBinTree)
		node.Value = v
		if _, err := Insert(root, node) ; err != nil {
			fmt.Println(err)
			return nil
		}
	}
	return root
}

//先不搞这么复杂,生成的是一颗不平衡的二叉树, 按中序生成
//生成树有问题，会生成值为nil的节点，并且其子树有值
func CreateTree(data []interface{})(root BinTree){
	// 根据树的高度,生成一刻完全的空二叉树
	high := math.Log2(float64(len(data)))
	var CreateFullEmptyTree func(high int, str string) BinTree
	index := 0
	CreateFullEmptyTree = func(level int, str string) BinTree {
		if level < 0 || index >= len(data) {
			return nil
		}
		node := new(BaseBinTree)
		node.SetLeftChild(CreateFullEmptyTree(level-1, "left"))
		if index < len(data) {
			node.Value = data[index]
		}
		// else{
		// 	//node.Value = fmt.Sprintf("level %d %s order is %d %p \n",level, str, index, node)
		// }
		//fmt.Printf("level %d %s order is %d %p\n",level, str, index, node)
		index ++
		node.SetRightChild( CreateFullEmptyTree(level-1, "right"))

		return node
	}
	FET := CreateFullEmptyTree(int(high), "root")
	// 往空二叉树里面提那些数据
	// func(root *Tree){
	// 	index := 0
	// 	for root != nil{
	// 		if root.Left != nil {
	// 			p := root.Left
	// 			for p.Right != nil && p.Right != root {
	// 				p = p.Right
	// 			}
	// 			if p.Right == nil {
	// 				p.Right = root
	// 				root = root.Left
	// 			} else {
	// 				if index < len(data) {
	// 					root.Value = data[index]
	// 					index ++
	// 				}
	// 				p.Right = nil
	// 				root = root.Right
	// 			}
	// 		} else {
	// 			if index < len(data) {
	// 				root.Value = data[index]
	// 				index ++
	// 			}
	// 			root = root.Right
	// 		}
	// 	}
	// }(FET)
	// 修剪空的叶子节点
	return FET
}